In combinatorics, a Sperner family (or Sperner system), named in honor of Emanuel Sperner, is a set system (F, E) in which no element is contained in another. Formally,
Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system or, if viewed from the hypergraph perspective, a clutter.
Contents |
The number of different Sperner families on a set of n elements is counted by the Dedekind numbers, the first few of which are
Although accurate asymptotic estimates are known for larger values of n, it is unknown whether there exists an exact formula that can be used to compute these numbers efficiently.
The k-subsets of an n-set form a Sperner family, the size of which is maximized when k = n/2. Sperner's theorem (a special case of Dilworth's theorem) states that these families are the largest possible Sperner families over an n-set. Formally, the theorem states that, for every Sperner family S over an n-set,
It is sometimes called Sperner's lemma, but that name also refers to another result on coloring. To differentiate the two results, the result on the size of a Sperner family is now more commonly known as Sperner's theorem.
A graded partially ordered set is said to have the Sperner property when one of its largest antichains is formed by a set of elements that all have the same rank; Sperner's theorem states that the poset of all subsets of a finite set, partially ordered by set inclusion, has the Sperner property.
The following proof is due to Lubell (see reference). Let sk denote the number of k-sets in S. For all 0 ≤ k ≤ n,
and, thus,
Since S is an antichain, we can sum over the above inequality from k = 0 to n and then apply the LYM inequality to obtain
which means
This completes the proof.
A clutter H is a hypergraph , with the added property that whenever and (i.e. no edge properly contains another). That is, the sets of vertices represented by the hyperedges form a Sperner family. Clutters are an important structure in the study of combinatorial optimization. The opposite notion of a clutter is an abstract simplicial complex, where every subset of an edge is contained in the hypergraph.
If is a clutter, then the blocker of H, denoted , is the clutter with vertex set V and edge set consisting of all minimal sets so that for every . It can be shown that (Edmonds & Fulkerson 1970), so blockers give us a type of duality. We define to be the size of the largest collection of disjoint edges in H and to be the size of the smallest edge in . It is easy to see that .
There is a minor relation on clutters which is similar to the minor relation on graphs. If is a clutter and , then we may delete v to get the clutter with vertex set and edge set consisting of all which do not contain v. We contract v to get the clutter . These two operations commute, and if J is another clutter, we say that J is a minor of H if a clutter isomorphic to J may be obtained from H by a sequence of deletions and contractions.